package day2_linkedlist.leetcode;

/**
 * @Author: yuisama
 * @Date: 2021/9/1 15:40
 * @Description:两两交换链表节点
 * https://leetcode-cn.com/problems/swap-nodes-in-pairs/
 * 给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
 * 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
 */
public class Num24 {
    // 递归法
//    public ListNode swapPairs(ListNode head) {
//        // 终止条件
//        if (head == null || head.next == null)
//            return head;
//        ListNode cur = head.next;
//        head.next = swapPairs(cur.next);
//        cur.next = head;
//        return cur;
//    }

    // 虚拟头结点
    public ListNode swapPairs(ListNode head) {
        ListNode dummyHead = new ListNode(-1,head);
        ListNode prev = dummyHead;
        if (head == null || head.next ==null)
            return head;
        // 保证还有成对节点
        while (prev.next != null && prev.next.next != null) {
            ListNode node1 = prev.next;
            ListNode node2 = node1.next;
            ListNode next = node2.next;
            node1.next = next;
            node2.next = node1;
            prev.next = node2;
            // 下次循环条件，p指向未判断偶节点前驱
            prev = node1;
        }
        return dummyHead.next;
    }
}
